题解 CF414B@洛谷 | 414B@Codeforces 【Mashmokh and ACM】

一道小清新动规题。

题意：求长度为 $k$ 的、最大数不超过 $n$ 的数列，满足 $a_i=a_{i-1}\times mul$（$2\le i\le n$ 且 $mul$ 为正整数）。

思路：

容易想到设计状态 $dp_{i,j}$ 表示长度为 $i$ 时最大数为 $j$ 的方案总数。

转移方程也比较好想，根据数列要求，枚举所有可能的倍数，加上对应方案的 $dp$ 值即可。即：$dp_{i,j}=\displaystyle\sum_{k\ \text{是}\ j\ \text{的因数}}dp_{i-1,k}$。由于因数不好统计，我们根据 $i,k$ 来反推即可。

但是还没有结束，虽然我们可以通过此题，但是作为一个优（du）秀（liu）的 OIer，你不觉得 $dp$ 数组这么大很多余吗？我们对于每一个 $i$，只用到了 $i-1$ 的 $dp$ 值，显然可以压缩空间啊！

考虑将 $dp_j$ 定义为最大数为 $j$ 的方案总数，原本的 $i$ 是没有必要存的。转移方程也没有特别大的变化。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2005, mod = 1e9+7;

ll n, k;
ll dp[N], tmp[N], ans;

int main() {
	scanf("%lld%lld", &n, &k);
	for(ll i=1;i<=n;i++) dp[i] = 1;
	for(ll cnts=2;cnts<=k;cnts++) {
		for(ll i=1;i<=n;i++) tmp[i] = 0;
		for(ll i=1;i<=n;i++) {
			for(ll j=1,_=i*j;_<=n;j++,_=i*j) tmp[_] = (tmp[_] + dp[i]) % mod;
		}
		for(ll i=1;i<=n;i++) dp[i] = tmp[i];
	}
	for(ll i=1;i<=n;i++) ans = (ans + dp[i]) % mod;
	printf("%lld\n", ans);
	return 0;
}